#include "common.h"
#include "ir-block.h"
#define VAR_TOTAL 4096

int totalVar=0;
varList init(){
    unsigned size=(totalVar+63u)/64u*sizeof(uLL);
    varList ret=malloc(size);
    memset(ret,0,size);
    return ret;
}
static void insertInterCode(InterCodes * pos,InterCodes * inst){
    inst->next=pos->next;
    if(!inst->next) end_op=inst; else inst->next->prev=inst;
    inst->prev=pos;pos->next=inst;
}
static void eraseInterCode(InterCodes * pos){
    static InterCodes * garbage_can=NULL;
    if(!pos->prev) first_op=pos->next;
    else pos->prev->next=pos->next;
    if(!pos->next) end_op=pos->prev;
    else pos->next->prev=pos->prev;
    pos->next=garbage_can;pos->prev=NULL;garbage_can=pos;
}
static void set_1(varList x,int pos){
    pos--;
    x[pos/64]|=1uLL<<(uLL)(pos%64);
    return;
}
static void set_0(varList x,int pos){
    pos--;
    x[pos/64]&=~(1uLL<<(uLL)(pos%64));
    return;
}

static inline int chk_is_set(int kind){
    return (kind>=2&&kind<=8)||kind==CALL||kind==READ||kind==EXTRA_INST;
}
static void defUse(BB block){
    assert(BB);
    varList def=init(),use=init();
    block->in=init();block->out=init();
    block->def=def;block->use=use;
    for(InterCodes * now=block->last;now!=block->first;now=now->prev){
        InterCode inst=now->code;now->block=block;
        Operand x=inst.x,y=inst.y,z=inst.z;
        int nx=inst.nx,ny=inst.ny,nz=inst.nz;
        if(x&&x->kind==VARIABLE){
            int t=x->u.var_no;
            if(!nx&&(chk_is_set(inst.kind))) set_0(use,t),set_1(def,t);
            else set_1(use,t);
        }
        if(y&&y->kind==VARIABLE) set_1(use,y->u.var_no);
        if(z&&z->kind==VARIABLE) set_1(use,z->u.var_no);
    }
    return;
}

static void BBbuild(InterCodes * first,InterCodes * last){
    BB ret=malloc(sizeof(struct basic_block));
    ret->first=first;ret->last=last;
    defUse(ret);
    ret->nxt1=last->next;ret->nxt2=NULL;
    switch(last->code.kind){
        case RET: ret->nxt1=NULL;break;
        case GOTO: ret->nxt1=last->code.x->entry;
        case OP_IF: ret->nxt2=last->code.z->entry;
    }
    return;
}

static inline uLL er(uLL a,uLL b){return a^(a&b);}
static int BBDefUseUpdate(BB x){
    int ret=0;
    for(int i=0;i<(totalVar+63u)/64u;i++){
        uLL old=x->out[i];
        uLL new=0;
        if(x->nxt1) new=x->nxt1->block->in[i];
        if(x->nxt2) new|=x->nxt2->block->in[i];
        if(new^old) ret=1;
        x->out[i]=new;
        x->in[i]=er(x->out[i],x->def[i])|x->use[i]; 
    }
    return ret;
}

static BB block_relied[VAR_TOTAL];
static int newest_var[VAR_TOTAL];
struct{
    Operand x;
    int marked,realated_var[2];
    unsigned info;
    InterCodes * def;
}current_all[VAR_TOTAL];
#define USE_VAR 1
#define IS_CONSTANT 2
#define REF 4
static int total=0;
static int map[VAR_TOTAL][3][VAR_TOTAL][3][4];
static int set_new_var(Operand x,InterCodes * now,BB xx){
    if(!x||x->kind!=VARIABLE) return 0;
    total++;
    current_all[total].x=x;
    current_all[total].def=now;
    current_all[total].marked=0;
    current_all[total].realated_var[0]=current_all->realated_var[1]=0;
    current_all[total].info=0;
    int no=x->u.var_no;
    newest_var[no]=total;
    block_relied[no]=total;
}
static int get_new_var(Operand x,BB xx){
    if(!x||x->kind!=VARIABLE) return 0;
    int no=x->u.var_no;
    if(block_relied[no]==xx){
        int t=newest_var[no];
        while(current_all[t].marked&REF) t=current_all[t].info;
        return t;
    }
    return set_new_var(x,NULL,xx); 
}
void BBOptimizer(BB block){
    total=0;
    for(InterCodes * now=block->first;now!=block->last->next;now=now->next){
        InterCode inst=now->code;
        Operand x=inst.x,y=inst.y,z=inst.z;
        int nx=inst.nx,ny=inst.ny,nz=inst.nz;
        int ox,oy=get_new_var(y,block),oz=get_new_var(z,block);
        if(!nx&&chk_is_set(inst.kind)) ox=set_new_var(x,now,block);
        else ox=get_new_var(x,block);
        if(!ox) continue;
        current_all[ox].realated_var[0]=oy;
        current_all[oy].realated_var[1]=oz;
        int u=inst.kind;
        switch(u){
            case ADD:case SUB:case MUL:case OP_DIV:
                if((!oy||current_all[oy].marked&IS_CONSTANT)&&(!oz||current_all[oz].marked&IS_CONSTANT)){
                    current_all[ox].marked|=IS_CONSTANT;
                    unsigned yy=oy?current_all[oy].info:y->u.value;
                    unsigned zz=oz?current_all[oz].info:z->u.value;
                    if(u==ADD) current_all[ox].info=yy+zz;
                    else if(u==SUB) current_all[ox].info=yy-zz;
                    else if(u==MUL) current_all[ox].info=yy*zz;
                    else current_all[ox].info=yy/zz;
                }
                break;
            case ASSIGN:
                if(oy){
                    current_all[ox].marked|=REF;
                    current_all[ox].info=oy;
                }else{
                    current_all[ox].marked|=CONSTANT;
                    current_all[ox].info=y->u.value;
                }
            case 
        }
    }
}

static inline chk_is_interval(InterCodes * now){
    assert(now);
    int t=now->code.kind;
    if(t==RET||t==GOTO||t==OP_IF) return 1;
    if(!now->next) return 1;
    int t=now->next->code.kind;
    if(t==LABL||t==FUNC) return 1;
    return 0;
}
void BBscan(){
    InterCodes * now=first_op,* last=NULL;
    while(now){
        last=now->next;
        while(!chk_is_interval(last)) last=last->next;
        BBbuild(now,last);
        last=now->next;
    }
    int t=1;
    while(t){
        t=0;
        for(InterCodes * now=end_op;now;now=now->block->first->prev){
            int tt=BBDefUseUpdate(now->block);
            t=t||tt;
        }
    }

}